//https://leetcode-cn.com/problems/reorder-list/ 


//========================================
// 一  存储方法
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 #include<vector>
class Solution {
public:
    vector<ListNode*> ListNode_vector;
    void reorderList(ListNode* head) {
        if( head == NULL)
            return ;
        for(ListNode * node = head;node != NULL;node = node ->next)
            ListNode_vector.push_back(node);
        int Num = ListNode_vector.size();
        for(int i =0;i<(int)Num/2;i++)
        {
            ListNode_vector[i]->next = ListNode_vector[Num-i-1];
            ListNode_vector[Num-i-1]->next = ListNode_vector[i+1];
        }
        ListNode_vector[(int)Num/2]->next = NULL;
        
    }
};

// 执行用时：88 ms, 在所有 C++ 提交中击败了12.94的用户
//内存消耗：15.3 MB, 在所有 C++ 提交中击败了14.29%的用户

//递归求解

//https://leetcode-cn.com/problems/reorder-list/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-34/


 #include<vector>
class Solution {
public:
    
    ListNode * helper(ListNode * head,int len)
    {
         ListNode * out_node =NULL;
        if(len == 1)
        {
            out_node = head->next;
            head->next = NULL;
            return out_node;
        }
        if(len == 2)
        {
            out_node = head->next->next;
            head->next->next = NULL;
            return out_node;
        }
        
        ListNode * tail = helper(head->next,len-2);
        out_node = tail->next;
        tail ->next = head->next;
        head->next = tail;
        return out_node;
    }

    void reorderList(ListNode* head) {
        if(head == NULL)
            return ;
        ListNode* node = head;
        int Sum = 0;
        while(node)
        {
            Sum ++;
            node = node ->next;
        }
        helper( head,Sum);
    }
};

// 执行用时：48 ms, 在所有 C++ 提交中击败了70.03%的用户
// 内存消耗：14.7 MB, 在所有 C++ 提交中击败了14.29%的用户